洛谷题解 CF1716A 【2-3 Moves】

题意翻译

现在有一条坐标轴,你现在坐标为 $0$ ,你每步可以走 $+3,+2,-3,-2$ 个单位问最少经过几步可以到达坐标为 $n$ 的点

解题过程

好吧,这其实是找规律题(毕竟是A题嘛)

首先就先列举出前几个坐标的情况

$n=1$ 时,最少步数为 $2 \ (+3-2)$

$n=2$ 时,最少步数为 $1 \ (+2)$

$n=3$ 时,最少步数为 $1 \ (+3)$

$n=4$ 时,最少步数为 $2 \ (+2+2)$

$n=5$ 时,最少步数为 $2 \ (+2+3)$

$n=6$ 时,最少步数为 $2 \ (+3+3)$

$n=7$ 时,最少步数为 $3 \ (+2+2+3)$

$n=8$ 时,最少步数为 $3 \ (+2+3+3)$

$n=9$ 时,最少步数为 $3 \ (+3+3+3)$

$……$

观察上面的情况,不难发现 $n$ 每增加三个单位最少步数 $+1$(除了在 ${1,2,3}$ 这一段里 $n=1$ 时最少步数为 $1$ )

其实如果不放心的话还可以再往下列举 (比赛时我列到了15)

用式子表示大概就是 $\operatorname{ans} = \begin{cases} 2 \ (n=1) \\ n/3 \ (n \bmod \ 3 =0)\\ n/3+1 \ (n \bmod \ 3\neq 0)\end{cases} $

代码实现


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include<iostream>
#include<cstdio>
using namespace std;

int n,t,ans=0;

int main()
{
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%d",&n);
if(n==1)
{
printf("2\n");
}
else
{
if(n%3!=0)
{
ans=n/3+1;
}
else
{
ans=n/3;
}
printf("%d\n",ans);
}

}
scanf("%d",&n);
return 0;
}

题目详见:https://www.luogu.com.cn/problem/show?pid=CF716A